public class test4 {
    //LCR.078 合并k个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists ,int left,int right){
        if(left>right) return null;
        if(left==right) return lists[left];
        //获取中间结点
        int mid = (left+right)/2;
        //分治
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        //合并两个有序链表
        return mergeTwoLists(l1,l2);

    }
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        //创建虚拟头结点
        ListNode newhead = new ListNode(0);
        ListNode prev = newhead;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while(cur1!=null && cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        //处理可能剩余的结点
        if(cur1!=null) prev.next = cur1;
        if(cur2!=null) prev.next = cur2;

        return newhead.next;
    }
}
